{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "运用多线程实现并发，其中一个好处是，它具备潜能，可以简单、直接地共享数据。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3.1 线程间共享数据的问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "归根结底，多线程共享数据的问题多由数据改动引发。如果所有共享数据都是只读数据，就不会有问题。因为，若数据被某个线程读取，无论是否存在其他线程也在读取，该数据都不会受到影响。然而，如果多个线程共享数据，只要一个线程开始改动数据，就会带来很多隐患，产生麻烦。鉴于此，我们必须小心、谨慎，保证一切都正确运作。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "为了帮助程序员分析代码，“不变量”（invariant）被广泛使用，它是一个针对某一特定数据的断言，该断言总是成立的，例如“这个变量的值即为链表元素的数目”。数据更新往往会破坏这些不变量，尤其是涉及的数据结构稍微复杂，或者数据更新需要改动的值不止一个时。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "考察双向链表，其每个节点都持有两个指针，分别指向自身前方（previous）和后方（next）的节点。故此，存在一个**不变量**：若我们从节点 A 的 next 指针到达另一节点B，则 B 的 previous 指针应该指向节点 A。\n",
    "\n",
    "为了从双向链表中删除某个节点，它两侧相邻节点的指针都要更新，指向彼此。只要其中一个相邻节点先行更新，不变量即被破坏，直到另一个节点也更新。更新的全部操作完成后，不变量又重新成立。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "从双向链表删除一个节点的步骤如图 3.1 所示。<br/>\n",
    "\n",
    "<img src=\"./images/3.1.png\" alt=\"3.1 从双向链表删除一个节点的步骤\" style=\"zoom:50%;\" />\n",
    "\n",
    "步骤 a：识别需要删除的节点，称之为 N。<br/>\n",
    "步骤 b：更新前驱节点中本来指向 N 的指针，令其改为指向 N 的后继节点。<br/>\n",
    "步骤 c：更新后继节点中本来指向 N 的指针，令其改为指向 N 的前驱节点。<br/>\n",
    "步骤 d：删除节点 N。<br/>\n",
    "\n",
    "从图 3.1 可见，在步骤 b 和步骤 c 之间，正向指针与逆向指针不一致，不变量被破坏。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**改动线程间的共享数据，可能导致的最简单的问题是破坏不变量**。\n",
    "\n",
    "假如某线程正在读取双向链表，另一线程同时在删除节点，而我们没有采取专门措施保护不变量，那么执行读取操作的线程很可能遇见未被完全删除的节点（只改动了一个指针，见图3.1 的步骤 b），不变量遂被破坏。破坏不变量可能引发各种各样的后果。在图 3.1 中，如果线程从左往右读取链表，它就会跳过正在被删除的节点；另一种情况是，若第二个线程正试图删除最右方的节点，则可能对链表造成永久损坏，最终令程序崩溃。无论运行结果如何，图 3.1 举例说明了并发代码中一种最常见的错误成因：**条件竞争**（race condition）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 条件竞争"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在并发编程中，操作由两个或多个线程负责，它们争先让线程执行各自的操作，而结果取决于它们执行的相对次序，所有这种情况都是条件竞争。\n",
    "\n",
    "很多时候，这是良性行为，因为全部可能的结果都可以接受，即便线程变换了相对次序。例如，两个线程向队列添加数据项以待处理，只要维持住系统的不变量，先添加哪个数据项通常并不重要。\n",
    "\n",
    "**当条件竞争导致不变量被破坏时，才会产生问题**，正如前面举例的双向链表。当论及并发时，条件竞争通常特指恶性条件竞争。良性条件竞争不会引起问题，我们不感兴趣。C++标准还定义了术语“数据竞争”（data race）：并发改动单个对象而形成的特定的条件竞争（详见 5.1.2 节）。数据竞争会导致未定义行为，让人忧虑。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "诱发恶性条件竞争的典型场景是，要完成一项操作，却需改动两份或多份不同的数据，如上例中的两个链接指针。\n",
    "\n",
    "因为操作涉及两份独立的数据，而它们只能用单独的指令改动，当其中一份数据完成改动时，别的线程有可能不期而访。\n",
    "\n",
    "因为满足条件的时间窗口短小，所以条件竞争往往既难察觉又难复现。若改动操作是由连续不间断的 CPU指令完成的，就不太有机会在任何的单次运行中引发问题，即使其他线程正在并发访问数据。只有按某些次序执行指令才可能引发问题。随着系统负载加重及执行操作的次数增多，这种次序出现的机会也将增加。“屋漏偏逢连夜雨”几乎难以避免，且这些问题偏偏会在最不合时宜的情况下出现。恶性条件竞争普遍“挑剔”出现的时机，当应用程序在调试环境下运行时，它们常常会完全消失，因为调试工具影响了程序的内部执行时序，哪怕只影响一点点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "若读者编写多线程程序，恶性条件竞争很可能成为致命伤；采用并发技术的软件会涉及许多复杂的逻辑，其目的正是避开恶性条件竞争。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 防止恶性条件竞争"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们有几种方法防止恶性条件竞争。*最简单的就是采取保护措施*包装数据结构，确保不变量被破坏时，中间状态只对执行改动的线程可见。在其他访问同一数据结构的线程的视角中，这种改动要么尚未开始，要么已经完成。C++标准库提供了几种方式实现这样的机制，本章将会讲解。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*另一种方法*是，修改数据结构的设计及其不变量，由一连串不可拆分的改动完成数据变更，每个改动都维持不变量不被破坏。这通常被称为无锁编程，难以正确编写。如果读者从事这一层面的开发工作，就要探究内存模型的微妙细节，以及区分每个线程可以看到什么数据集，两者都可能很复杂。内存模型会在第 5 章说明，第 7 章讨论无锁编程。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*还有一种防止恶性条件竞争的方法*，将修改数据结构当作事务（transaction）来处理，类似于数据库在一个事务内完成更新：把需要执行的数据读写操作视为一个完整序列，先用事务日志存储记录，再把序列当成单一步骤提交运行。若别的线程改动了数据而令提交无法完整执行，则事务重新开始。这称为软件事务内存（Software Transactional Memory，STM）。在编写本书时，该研究依然相当活跃。但是，因为 C++没有直接支持STM，所以本书不会涵盖该议题（C++标准委员会已公布了一份技术规约，内容正是软件事务内存的 C++扩展）。事务处理的基本思想是，单独操作，然后一步提交完成，相关内容我们会在后文展开。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3.2 用互斥保护共享数据"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "假定有一个用于共享的数据结构，与 3.1 节中的双向链表相似，我们要保护它，避免条件竞争，并防止不变量被破坏。如果我们能标记访问该数据结构的所有代码，令各线程在其上相互排斥（mutually exclusive），那么，只要有线程正在运行标记的代码，任何别的线程意图访问同一份数据，则必须等待，直到该线程完事，这岂不妙哉？如此一来，除了正在改动数据的线程自身，任何线程都无法看见不变量被破坏。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这并非异想天开，运用名为**互斥**（mutual exclusion，略作 mutex）的同步原语（synchronization primitive）就能达到我们想要的效果。访问一个数据结构前，先锁住与数据相关的互斥；访问结束后，再解锁互斥。C++线程库保证了，一旦有线程锁住了某个互斥，若其他线程试图再给它加锁，则须等待，直至最初成功加锁的线程把该互斥解锁。这确保了全部线程所见到的共享数据是自洽的（self-consistent），不变量没有被破坏。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "互斥是 C++最通用的共享数据保护措施之一，但非万能的灵丹妙药。我们务必妥善地组织和编排代码，从而正确地保护共享数据（见 3.2.2 节），同时避免接口固有的条件竞争（见 3.2.3 节）。互斥本身也有问题，表现形式是死锁（见 3.2.4 节）、对数据的过保护或欠保护（见 3.2.8 节）。下面从基础知识开始讲解。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 在 C++中使用互斥 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在 C++中，我们通过构造 `std::mutex` 的实例来创建互斥，调用成员函数 `lock()`对其加锁，调用 `unlock()`解锁。\n",
    "\n",
    "但我不推荐直接调用成员函数的做法。原因是，若按此处理，那我们就必须记住，在函数以外的每条代码路径上都要调用 `unlock()`，包括由于异常导致退出的路径。取而代之，C++标准库提供了类模板 `std::lock_guard<>`，针对互斥类融合实现了 RAII 手法：在构造时给互斥加锁，在析构时解锁，从而保证互斥总被正确解锁。代码清单 3.1 展示了如何用 `std::mutex` 类和 `std::lock_guard` 类保护链表，使之能同时被多个线程访问。两个类都在头文件`<mutex>`里声明。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// https://godbolt.org/z/Gv6835qMs\n",
    "\n",
    "#include <algorithm>\n",
    "#include <iostream>\n",
    "#include <list>\n",
    "#include <mutex>\n",
    "\n",
    "std::list<int> some_list; // 1\n",
    "std::mutex some_mutex; // 2\n",
    "\n",
    "void add_to_list(int new_value) {\n",
    "    std::lock_guard<std::mutex> guard(some_mutex); // 3\n",
    "    some_list.push_back(new_value);\n",
    "}\n",
    "\n",
    "bool list_contains(int value_to_find) {\n",
    "    std::lock_guard<std::mutex> guard(some_mutex); // 4\n",
    "    return std::find(some_list.begin(), some_list.end(), value_to_find) !=\n",
    "           some_list.end();\n",
    "}\n",
    "\n",
    "int main() {\n",
    "    add_to_list(42);\n",
    "    std::cout << \"contains(1)=\" << list_contains(1)\n",
    "              << \", contains(42)=\" << list_contains(42) << std::endl;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "代码清单 3.1 中有一个独立的全局变量①，由对应的 `std::mutex` 实例保护（另一个全局变量）②。函数 `add_to_list()`③和函数 `list_contains()`④内部都使用了 `std::lock_guard< std::mutex>`，其意义是使这两个函数对链表的访问互斥：假定 `add_to_list()`正在改动链表，若操作进行到一半，则 `list_contains()`绝对看不见该状态。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "C++17 引入了一个新特性，名为类模板参数推导（class template argument deduction），顾名思义，对于 `std::lock_guard<>`这种简单的类模板，模板参数列表可以忽略。\n",
    "\n",
    "如果编译器支持 C++17 标准，则③和④都能简化成“`std::lock_guard guard(some_mutex);`”。\n",
    "\n",
    "我们将在 3.2.4 节看到，C++17 还引入了 `std::scoped_lock`，它是增强版的 `lock_guard`。因此，在 C++17 环境下，上述语句完全可以写成“`std::scoped_lock guard(some_mutex);`”。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "为了令代码清晰、易读，也为了兼容旧的编译器，我们继续使用 `std::lock_guard`，并在其他代码片段中写明模板参数。\n",
    "\n",
    "尽管有些场景适合模仿本例使用全局变量，不过大多数场景下的普遍做法是，将互斥与受保护的数据组成一个类。这是面向对象设计准则的典型运用：将两者放在同一个类里，我们清楚表明它们互相联系，还能封装函数以增强保护。\n",
    "\n",
    "本例的 `add_to_list()`和 `list_contains()`将被改写为类的成员函数，而互斥和受保护的共享数据都会变成类的私有成员。按此处理，就非常便于确定哪些代码可以访问数据、哪些代码需要锁住互斥。类的所有成员函数在访问任何数据成员之前，假如都先对互斥加锁，并在完成访问后解锁，共享数据就可很好地受到全方位保护。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可惜事与愿违，敏锐的读者可能已经注意到，如果成员函数返回指针或引用，指向受保护的共享数据，那么即便成员函数全都按良好、有序的方式锁定互斥，仍然无济于事，因为保护已被打破，出现了大漏洞。只要存在任何能访问该指针和引用的代码，它就可以访问受保护的共享数据（也可以修改），而无须锁定互斥。所以，若利用互斥保护共享数据，则需谨慎设计程序接口，从而确保互斥已先行锁定，再对受保护的共享数据进行访问，并保证不留后门。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 组织和编排代码以保护共享数据 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如读者所见，利用互斥保护共享数据并不太简单，我们不能把 `std::lock_guard` 对象化作“铁拳”，对准每个成员函数施予“重击”。\n",
    "\n",
    "一旦出现游离的指针或引用，这种保护就全部形同虚设。不管成员函数通过什么“形式”—无论是返回值，还是输出参数（out parameter）—向调用者返回指针或引用，指向受保护的共享数据，就会危及共享数据安全。一定程度上，检查游离指针或引用并不困难，若能防止上述情形出现，则共享数据无恙。\n",
    "\n",
    "只要继续深究，我们即可发现事情并非那么简单、直接—完全不是。我们除了要检查成员函数，防止向调用者传出指针或引用，还必须检查另一种情况：若成员函数在自身内部调用了别的函数，而这些函数却不受我们掌控，那么，也不得向它们传递这些指针或引用。这种情况同样危险：这些函数有可能将指针或引用暂存在别处，等到以后脱离了互斥保护再投入使用。在运行期，假如这些函数作为函数指针充当参数，或以别的形式提供给上述成员函数，那就格外危险了，如代码清单 3.2 所示。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// 3.2 \n",
    "\n",
    "#include <mutex>\n",
    "#include <string>\n",
    "\n",
    "class some_data {\n",
    "    int a;\n",
    "    std::string b;\n",
    "\n",
    "   public:\n",
    "    void do_something() {}\n",
    "};\n",
    "\n",
    "class data_wrapper {\n",
    "   private:\n",
    "    some_data data;\n",
    "    std::mutex m;\n",
    "\n",
    "   public:\n",
    "    template <typename Function>\n",
    "    void process_data(Function func) {\n",
    "        std::lock_guard<std::mutex> l(m);\n",
    "        func(data); // 1: 向使用者提供的函数传递受保护共享数据\n",
    "    }\n",
    "};\n",
    "\n",
    "some_data* unprotected;\n",
    "\n",
    "void malicious_function(some_data& protected_data) {\n",
    "    unprotected = &protected_data;\n",
    "}\n",
    "\n",
    "data_wrapper x;\n",
    "\n",
    "void foo() {\n",
    "    x.process_data(malicious_function); // 2. 传入恶意函数\n",
    "    unprotected->do_something(); // 3. 以无保护方式访问本应受保护的共享数据\n",
    "}\n",
    "\n",
    "int main() { foo(); }\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在本例中，`process_data()`函数内的代码显然没有问题，由 `std::lock_guard` 很好地保护，然而，其参数 func 是使用者提供的函数①。\n",
    "\n",
    "换言之，`foo()`中的代码可以传入`malicious_function`②，接着，就能绕过保护，调用 `do_something()`，而没有锁住互斥③。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "本质上，以上代码的问题在于，它未能真正实现我们原有的设想：把所有访问共享数据的代码都标记成互斥。\n",
    "\n",
    "上例中，我们遗漏了 `foo()`，调用 `unprotected->do_something()`的代码未被标记。无奈，C++线程库对这个问题无能为力；只有靠我们自己—程序员—正确地锁定互斥，借此保护共享数据。从乐观的角度看，只要遵循下列指引即可应对上述情形：不得向锁所在的作用域之外传递指针和引用，指向受保护的共享数据，无论是通过函数返回值将它们保存到对外可见的内存，还是将它们作为参数传递给使用者提供的函数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这是使用互斥保护共享数据的常见错误，但错误远远不止这一个。我们会在 3.2.3节看到，即使共享数据已经受到互斥保护，却仍有可能发生条件竞争。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 发现接口固有的条件竞争 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "尽管运用了互斥或其他方式保护共享数据，条件竞争依然无法避免；我们仍须力保共享数据得到稳妥保护。\n",
    "\n",
    "再次考虑前文双向链表的例子，为了使线程安全地删除节点，我们必须禁止 3 个节点的并发访问：正要删除的节点和它两侧的邻居。若仅仅单独保护各节点的指针，则与没有使用互斥差不多，因为条件竞争仍可能发生。删除行为是完整的操作，只在单独步骤中保护单个节点不起作用，整体数据结构都要保护。\n",
    "\n",
    "针对此例，最简单的解决方法是，单独用一个互斥保护整个链表，如代码清单 3.1 所示。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "虽然整个链表上的单一操作是安全行为，我们却不能因此而摆脱麻烦。即便只涉及简单的接口，我们还是有可能遇到条件竞争。\n",
    "\n",
    "考虑代码清单 3.3 中的栈数据结构(本节所述的栈一律特指数据结构的栈容器，与可执行程序中的数据栈、调用栈或栈数据段无关)，它与`std::stack` 容器适配器相似。除了构造函数和 `swap()`函数，我们只能对 `std::stack` 进行 5种操作：用 `push()`压入新元素、用 `pop()`弹出栈顶元素、用 `top()`读取栈顶元素、用 `empty()`检测栈是否为空，以及用 `size()`读取栈内元素的数量。若我们修改 `top()`的实现，令它返回元素的副本而非引用（遵循 3.2.2 节的准则），还用互斥保护内部数据，但是，该函数接口同样受制于条件竞争。这是接口本身的问题，它不仅仅出现在基于互斥的实现中，无锁实现也会发生条件竞争。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// 3.3\n",
    "\n",
    "#include <deque>\n",
    "#include <cstddef>\n",
    "template<typename T,typename Container=std::deque<T> >\n",
    "class stack\n",
    "{\n",
    "public:\n",
    "    explicit stack(const Container&);\n",
    "    explicit stack(Container&& = Container());\n",
    "    template <class Alloc> explicit stack(const Alloc&);\n",
    "    template <class Alloc> stack(const Container&, const Alloc&);\n",
    "    template <class Alloc> stack(Container&&, const Alloc&);\n",
    "    template <class Alloc> stack(stack&&, const Alloc&);\n",
    "\n",
    "    bool empty() const;\n",
    "    size_t size() const;\n",
    "    T& top();\n",
    "    T const& top() const;\n",
    "    void push(T const&);\n",
    "    void push(T&&);\n",
    "    void pop();\n",
    "    void swap(stack&&);\n",
    "};\n",
    "\n",
    "int main()\n",
    "{}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这里的问题是，`empty()`和 `size()`的结果不可信。\n",
    "\n",
    "尽管，在某线程调用 `empty()`或 `size()`时，返回值可能是正确的。然而，一旦函数返回，其他线程就不再受限，从而能自由地访问栈容器，可能马上有新元素入栈，或者，现有的元素会立刻出栈，令前面的线程得到的结果失效而无法使用。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "有一种特殊情况：我们没共享栈容器。如果先由 `empty()`判定栈非空，接着调用 `top()`访问栈顶元素，那么，这是安全的行为。代码如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "stack<int> s; \n",
    "if(!s.empty()) {\n",
    "  int const value = s.top();\n",
    "  s.pop();\n",
    "  do_something(value); \n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在空栈上调用 `top()`会导致未定义行为，上面的代码已做好数据防备。对单线程而言，它既安全，又符合预期。可是，只要涉及共享，这一连串调用便不再安全。因为，在 `empty()`①和 `top()`②之间，可能有另一个线程调用 `pop()`，弹出栈顶元素。毫无疑问，这正是典型的条件竞争。它的根本原因在于函数接口，即使在内部使用互斥保护栈容器中的元素，也无法防范。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如何解决上述问题？问题根源是接口设计，所以解决方法是变更接口。\n",
    "\n",
    "追问下去：应当怎么变更接口？\n",
    "\n",
    "最简单的方式是将 `top()`声明为一旦空栈调用，`top()`就抛出异常。虽然此法直击要害，但实际使用却很麻烦。原因是，按这样处理，尽管栈容器非空，即 `empty()`返回 `false`，却还是有可能在调用 `top()`②时抛出异常，我们仍须进行捕捉(注: 即便在调用 `empty()`时栈容器非空，函数返回 `false`，当前线程顺利进入 `if` 分支，但由于多线程访问，其他线程有可能同时执行了 `s.pop()`③，让栈容器变空，导致②处的 `s.top()`抛出异常。因此我们依旧要捕捉异常，将整个 `if` 语句置于 `try` 块中)。相反，假定栈容器原本已经全空，在此前提下执行 `top()`肯定抛出异常，相当于额外开销。而①处借`empty()`做判断防止了空栈调用 `top()`，那么 `if` 语句便成了优化手段，而非必要的设计。其实，依照上述方式，只有在 `empty()`和 `top()`两个调用之间，栈容器因多线程共享从非空状态转变为全空状态时，异常才会抛出。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "假如再仔细观察以上代码，就能发现还潜藏了另一竞争条件，但这次它发生在 `top()`②和 `pop()`③的调用之间。考虑两个线程，都在同一个栈容器 `s` 上同时运行这段代码。这种情形并不少见。借助多线程提升性能的常见方式是，让多线程在不同数据上运行相同的代码。在线程间切分工作，共享的栈容器是理想的工具（其实队列更常用，范例见第6 章和第 7 章）。假定栈上最开始只有两个元素，所以不必担心哪个线程会在 `empty()`和`top()`之间竞争。现在考虑下面可能的执行方式。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果栈容器内部具有互斥保护，任何时刻都只准许单一线程运行其成员函数，那么函数调用便交错有秩，而 `do_something()`也得以并发运行。\n",
    "\n",
    "表 3.1 列出了一种可能的执行次序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "source": [
    "| 线 程 甲 | 线 程 乙 |\n",
    "|---------|---------|\n",
    "| if(!s.empty()) | |\n",
    "| | if(!s.empty()) |\n",
    "| int const value = s.top(); | |\n",
    "| | int const value = s.top(); |\n",
    "| s.pop(); | |\n",
    "| do_something(value); | s.pop(); |\n",
    "| | do_something(value); |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如我们所见，假设只有这两个线程运行，并且在两个 `top()`调用之间不存在其他操作，那么栈容器不会被更改，两个线程会得到相同的值。另外，在 `top()`与 `pop()`的调用之间没有其他调用。结果，栈顶元素被读取了两次，但栈顶的第二个元素却始终未被读取就被丢弃。相比 `empty()`和 `top()`竞争导致的未定义行为，这是另一潜藏得更隐蔽的条件竞争。诱发错误的原因并不明显，它与后果之间的联系也难以被觉察。至于最终造成什么后果，显然还取决于 `do_something()`的内部具体操作。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这要求从根本上更改接口设计，其中一种改法是把 `top()`和 `pop()`组成一个成员函数，再采取互斥保护。\n",
    "\n",
    "- Tom Cargill 指出，对于栈容器中存储的对象，若其拷贝构造函数抛出异常，则可能导致该合成的成员函数出现问题。\n",
    "- Herb Sutter 从异常安全的角度出发，相当全面地解决了这个问题（虽然条件竞争的隐患依然存在，并给合成的成员函数带来了新问题）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "部分读者大概还没意识到问题所在，那么请考虑 `stack<vector<int>>`。\n",
    "\n",
    "请注意，`vector`容器会动态调整大小，因此，当我们复制 `vector` 容器时，C++标准库需在程序的堆数据段上分配更多内存，以便复制内容。假如系统负载过重或内存资源严重受限，内存分配可能失败，导致 `vector` 容器的拷贝构造函数抛出 `std::bad_alloc` 异常。若 `vector` 容器中的元素数量巨大，就很可能引发这种情况。同时，我们又假设 `pop()`函数的定义是：返回栈顶元素的值，并从栈上将其移除。隐患由此而来：只有在栈被改动之后，弹出的元素才返回给调用者，然而在向调用者复制数据的过程中，有可能抛出异常。万一弹出的元素已从栈上移除，但复制却不成功，就会令数据丢失！为了解决这个问题，`std::stack` 接口的设计者将操作一分为二：先用 `top()`获取栈顶元素，随后再用 `pop()`把它移出栈容器，因此，即便我们无法安全地复制数据，它还是存留在栈上。倘若问题的诱因是堆数据段的内存不足，也许应用程序可以释放一些内存，然后重新尝试。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "无奈，我们恰恰要避免分割操作才可以消除条件竞争！万幸还有别的方法消除条件竞争，但它们都不完美。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 方法 1：传入引用"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "方法 1 是借一个外部变量接收栈容器弹出的元素，将指涉它的引用通过参数传入`pop()`调用。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "std::vector<int> result;\n",
    "some_stack.pop(result);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这在许多情况下行之有效，但还是有明显短处。如果代码要调用 `pop()`，则须先依据栈容器中的元素型别构造一个实例，将其充当接收目标传入函数内。\n",
    "\n",
    "对于某些型别，构建实例的时间代价高昂或耗费资源过多，所以不太实用。在另一些型别的栈元素的内部代码中，其构造函数不一定带有参数，故此法也并不总是可行。最后，这种方法还要求栈容器存储的型别是可赋值的（assignable）。该限制不可忽视：许多用户定义的型别并不支持赋值，尽管它们支持移动构造甚至拷贝构造（准许 `pop()`按值返回）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 方法 2：提供不抛出异常的拷贝构造函数，或不抛出异常的移动构造函数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "假设 `pop()`按值返回，若它抛出异常，则牵涉异常安全的问题只会在这里出现。许多型别都含有不抛出异常的拷贝构造函数。另外，随着 C++标准新近引入的右值引用（见附录 A.1 节）得到支持，更多型别将具备不抛出异常的移动构造函数（即便它们的拷贝构造函数会抛出异常）。对于线程安全的栈容器，一种可行的做法是限制其用途，只允许存储上述型别的元素按值返回，且不抛出异常。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这虽然安全，效果却不理想。尽管我们只要利用 `std::is_nothrow_copy_constructible`和 `std::is_nothrow_move_constructible` 这两个型别特征（type trait），便可在编译期对某个型别进行判断，确定它是否含有不抛出异常的拷贝构造函数，以及是否含有不抛出异常的移动构造函数，然而栈容器的用途还是会很受限。就用户定义的型别而言，其中一些含有会抛出异常的拷贝构造函数，却不含移动构造函数，另一些则含有拷贝构造函数和/或移动构造函数，而且不抛出异常。相比之下，前者数量更多（随着开发者逐渐接受C++11 支持右值引用，这种状况会改变）。假若线程安全的栈容器无法存储这些型别，那实在可惜。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 为什么异常影响线程安全?\n",
    "\n",
    "1. 资源管理和状态一致性\n",
    "\n",
    "当异常在多线程环境中发生时，可能会导致：\n",
    "\n",
    "- **状态不一致**：操作可能只完成一部分就被异常中断，导致对象处于无效或不完整状态\n",
    "- **锁未释放**：如果不使用RAII机制（如`std::lock_guard`），异常发生时锁可能不会被释放\n",
    "- **资源泄漏**：内存或其他系统资源可能无法正确释放\n",
    "\n",
    "```C++\n",
    "// 不安全的代码示例\n",
    "void thread_unsafe_function() {\n",
    "    mutex.lock();  // 获取锁\n",
    "    // 如果下面的代码抛出异常，锁将永远不会被释放\n",
    "    data.push_back(new_item);  // 可能抛出异常\n",
    "    mutex.unlock();  // 如果上面抛异常，这行不会执行\n",
    "}\n",
    "```\n",
    "\n",
    "2. 原子操作被破坏\n",
    "\n",
    "考虑线程安全的栈实现中的`pop()`操作：\n",
    "\n",
    "```C++\n",
    "T pop() {\n",
    "    std::lock_guard<std::mutex> lock(m);  // 获取锁\n",
    "    if(data.empty()) throw empty_stack();\n",
    "    T result = data.top();  // 如果T的拷贝构造函数抛出异常？\n",
    "    data.pop();  // 此行可能不会执行\n",
    "    return result;\n",
    "}\n",
    "```\n",
    "\n",
    "如果`T`的拷贝构造函数抛出异常：\n",
    "\n",
    "- 栈的顶部元素已经被读取\n",
    "- 但还没有从栈中移除\n",
    "- 异常导致函数提前返回，栈的状态不变\n",
    "- 但从用户角度看，`pop()`操作失败了，却没有正确地恢复状态\n",
    "\n",
    "3. 死锁风险增加\n",
    "\n",
    "异常可能导致锁的获取和释放顺序被破坏，增加死锁风险：\n",
    "\n",
    "```C++\n",
    "void process_data() {\n",
    "    lock_guard<mutex> lock1(mutex1);\n",
    "    try {\n",
    "        do_something();  // 可能抛出异常\n",
    "        lock_guard<mutex> lock2(mutex2);\n",
    "        do_something_else();\n",
    "    } catch(...) {\n",
    "        // 异常处理可能引入新的锁，或改变锁的获取顺序\n",
    "        lock_guard<mutex> lock3(mutex3);\n",
    "        handle_error();\n",
    "    }\n",
    "}\n",
    "```\n",
    "\n",
    "4. 多线程异常传播问题\n",
    "\n",
    "- 在一个线程中抛出但未捕获的异常会终止整个程序\n",
    "- 异常不能跨线程边界传播，导致难以处理跨线程错误\n",
    "\n",
    "```C++\n",
    "std::thread t([]() {\n",
    "    try {\n",
    "        // 线程工作...\n",
    "    } catch(...) {\n",
    "        // 异常只能在当前线程内处理\n",
    "        // 无法传递给创建此线程的线程\n",
    "    }\n",
    "});\n",
    "```\n",
    "\n",
    "5. 具体案例：线程安全栈的实现\n",
    "\n",
    "考虑按值返回元素的线程安全栈：\n",
    "\n",
    "```C++\n",
    "template<typename T>\n",
    "class threadsafe_stack {\n",
    "public:\n",
    "    T pop() {\n",
    "        std::lock_guard<std::mutex> lock(m);\n",
    "        if(data.empty()) throw empty_stack();\n",
    "        T result = data.top();  // 可能抛出异常\n",
    "        data.pop();  // 如果上面抛异常，这行不会执行\n",
    "        return result;\n",
    "    }\n",
    "private:\n",
    "    std::stack<T> data;\n",
    "    std::mutex m;\n",
    "};\n",
    "```\n",
    "\n",
    "解决方案之一是使用不抛出异常的构造函数：\n",
    "\n",
    "```C++\n",
    "template<typename T>\n",
    "class threadsafe_stack {\n",
    "public:\n",
    "    // 只有当T有不抛出异常的拷贝或移动构造函数时才启用此方法\n",
    "    template<typename U = T>\n",
    "    typename std::enable_if<\n",
    "        std::is_nothrow_copy_constructible<U>::value ||\n",
    "        std::is_nothrow_move_constructible<U>::value,\n",
    "        U>::type\n",
    "    pop() {\n",
    "        std::lock_guard<std::mutex> lock(m);\n",
    "        if(data.empty()) throw empty_stack();\n",
    "        U result(std::move_if_noexcept(data.top()));\n",
    "        data.pop();\n",
    "        return result;\n",
    "    }\n",
    "    \n",
    "    // 其他pop方法...\n",
    "private:\n",
    "    std::stack<T> data;\n",
    "    std::mutex m;\n",
    "};\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 方法 3：返回指针，指向弹出的元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "方法3是返回指针，指向弹出的元素，而不是返回它的值。其优点是指针可以自由地复制，不会抛出异常。因此 Cargill 所指出的异常问题可以避免。但此法存在缺点：在返回的指针所指向的内存中，分配的目标千差万别，既可能是复杂的对象，也可能是简单的型别，如 `int`，这就要求我们采取措施管理内存，但这便构成了额外的负担，也许会产生超过按值返回相应型别的开销。\n",
    "\n",
    "若函数接口采取上述方法，则指针型别`std::shared_ptr` 是不错的选择：首先，它避免了内存泄漏，因为只要该指针的最后一份副本被销毁，被指向的对象也随之释放；其次，内存分配策略由 C++标准库全权管控，调用者不必亲自操作 `new` 和 `delete` 操作符，否则我们只能运用 `new` 操作符，为栈上每个元素逐一分配内存。相比原来的非线程安全版本，这种手动方法产生的额外开销非常低。鉴于此，采用 `std::shared_ptr` 对性能进行优化意义重大。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 方法 4：结合方法 1 和方法 2，或结合方法 1 和方法 3 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "代码绝不能丧失灵活性，泛型代码更应如此。若我们选定了方法 2 或方法 3，那么再一并提供方法 1 便相对容易。这种方法给予代码使用者更多选择，他们可以从中挑选最适合的方法，只承担甚小的额外代价。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5．类定义示例：线程安全的栈容器类"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "代码清单 3.4 展示了栈容器类的简要定义，它消除了接口的条件竞争。其成员函数`pop()`具有两份重载，分别实现了方法 1 和方法 3：一份接收引用参数，指向某外部变量的地址，存储弹出的值；另一份返回 `std::shared_ptr<>`。类的接口很简单，只有 `push()`和 `pop()`两个函数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// 代码清单 3.4 线程安全的栈容器类（简要定义）\n",
    "\n",
    "#include <exception>\n",
    "#include <memory> // 1. std::shared_ptr<>在<memory>头文件内定义\n",
    "\n",
    "struct empty_stack : std::exception {\n",
    "    const char* what() const throw();\n",
    "};\n",
    "\n",
    "template <typename T>\n",
    "class threadsafe_stack {\n",
    "   public:\n",
    "    threadsafe_stack();\n",
    "    threadsafe_stack(const threadsafe_stack&);\n",
    "    threadsafe_stack& operator=(const threadsafe_stack&) = delete; // 2. 将赋值运算符删除\n",
    "\n",
    "    void push(T new_value);\n",
    "    std::shared_ptr<T> pop();\n",
    "    void pop(T& value);\n",
    "    bool empty() const;\n",
    "};\n",
    "\n",
    "int main() {}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "简化接口换来了最大的安全保证，甚至还能限制栈容器的整体操作。\n",
    "\n",
    "由于赋值运算符被删除②（详见附录 A.2 节），因此栈容器本身不可赋值。它也不具备 `swap()`函数(参考 `std::stack::swap()`。其功能是互换两个栈容器所装载的元素，将全部元素放置到对方容器内)，但它可被复制（前提是所装载的元素能被复制）。在空栈上调用 `pop()`会抛出 `empty_stack`异常。所以，即使栈容器在调用 `empty()`之后被改动，一切仍能正常工作。方法3的解释已提及，`std::shared_ptr` 让我们不必亲自管理内存分配。如果有需要，还能借其进行优化以避免过度操作 `new` 操作符和 `delete` 操作符。于是原有的 5 个栈操作变成 3 个—`push()`、`pop()`和 `empty()`，甚至 `empty()`也是多余的。简化接口让我们得以确保互斥能针对完整操作而锁定，从而更好地掌控数据。代码清单 3.5 给出了一个栈容器类的详尽定义，它由包装 `std::stack<>`得出。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// 代码清单 3.5 线程安全的栈容器类（详尽定义）\n",
    "// https://godbolt.org/z/P5qf1hb3M\n",
    "\n",
    "#include <exception>\n",
    "#include <memory>\n",
    "#include <mutex>\n",
    "#include <stack>\n",
    "\n",
    "struct empty_stack : std::exception {\n",
    "  const char *what() const throw() { return \"empty stack\"; }\n",
    "};\n",
    "\n",
    "template <typename T> class threadsafe_stack {\n",
    "private:\n",
    "  std::stack<T> data;\n",
    "  mutable std::mutex m;\n",
    "\n",
    "public:\n",
    "  threadsafe_stack() {}\n",
    "  threadsafe_stack(const threadsafe_stack &other) {\n",
    "    std::lock_guard<std::mutex> lock(other.m);\n",
    "    data = other.data; // 1. 在构造函数的函数体（constructor body）内进行复制操作\n",
    "  }\n",
    "  threadsafe_stack &operator=(const threadsafe_stack &) = delete;\n",
    "\n",
    "  void push(T new_value) {\n",
    "    std::lock_guard<std::mutex> lock(m);\n",
    "    data.push(new_value);\n",
    "  }\n",
    "  std::shared_ptr<T> pop() {\n",
    "    std::lock_guard<std::mutex> lock(m);\n",
    "    if (data.empty()) { // 2. 试图弹出前检查是否为空栈\n",
    "      throw empty_stack();\n",
    "    }\n",
    "\n",
    "    std::shared_ptr<T> const res(std::make_shared<T>(data.top())); // 3.改动栈容器前设置返回值\n",
    "    data.pop();\n",
    "    return res;\n",
    "  }\n",
    "  void pop(T &value) {\n",
    "    std::lock_guard<std::mutex> lock(m);\n",
    "    if (data.empty())\n",
    "      throw empty_stack();\n",
    "    value = data.top();\n",
    "    data.pop();\n",
    "  }\n",
    "  bool empty() const {\n",
    "    std::lock_guard<std::mutex> lock(m);\n",
    "    return data.empty();\n",
    "  }\n",
    "};\n",
    "\n",
    "int main() {\n",
    "  threadsafe_stack<int> si;\n",
    "  si.push(5);\n",
    "  si.pop();\n",
    "  if (!si.empty()) {\n",
    "    int x;\n",
    "    si.pop(x);\n",
    "  }\n",
    "}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这个栈容器的实现是可复制的，拷贝构造函数先在源对象上锁住互斥，再复制内部的 `std::stack`。我们没采用成员初始化列表（member initializer list），而是在构造函数的函数体内进行复制操作①，从而保证互斥的锁定会横跨整个复制过程。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "前文曾讨论过 `top()`和 `pop()`，由于锁的粒度太小，需要被保护的操作没有被完整覆盖，因此出现接口的恶性条件竞争。如果锁的粒度太大，互斥也可能出现问题。\n",
    "\n",
    "极端的情形是，用单一的全局互斥保护所有共享数据。在共享大量数据的系统中，这么做会消除并发带来的任何性能优势，原因是多线程系统由此受到强制限定，任意时刻都只准许运行其中一个线程，即便它们访问不同的数据。回顾第一个支持多处理器系统的 Linux内核版本，其设计正是如此，仅使用了一个全局内核锁（global kernel lock）。虽然它能工作，但事实上，尽管一个系统配备了双处理器，可性能往往不如两个单处理器系统之和，配备了 4 个处理器的系统性能则更糟，对比 4 个单处理器系统之和，它只能望尘莫及。有些线程被调度到额外的处理器上运行，但内核资源的争抢过于激烈，导致难以有效工作。Linux 内核的后续版本改进了加锁策略，粒度更精细，遂大幅减少了资源争抢，四处理器系统性能就理想多了，非常接近单处理器系统性能的 4 倍。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "精细粒度的加锁策略也存在问题。为了保护同一个操作涉及的所有数据，我们有时候需要锁住多个互斥。前文提到过，在某些场景下的正确做法是，在互斥的保护范围内增大数据粒度，从而只需锁定一个互斥。然而这种处理方式也可能不合时宜，例如，若要保护同一个类的多个独立的实例，则应该分别使用多个互斥。如果在此情况下提升加锁的层级，我们其实是把加锁的责任推卸给了使用者，或不得不用一个互斥保护该类的全部实例，两者皆不是可取之道。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "假如我们终须针对某项操作锁住多个互斥，那就会让一个问题藏匿起来，伺机进行扰乱：死锁。条件竞争是两个线程同时抢先运行，死锁则差不多是其反面：两个线程同时互相等待，停滞不前。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 死锁：问题和解决方法 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "假设一件玩具由两部分组成，需要同时配合才能玩，譬如玩具鼓和鼓槌；又假设有两个小孩都喜欢这件玩具。倘若其中一个孩子拿到了玩具鼓和鼓槌，那他就能尽兴地一直敲鼓，敲烦了才停止。如果另一个孩子也想玩，便须等待，即使感到难受也没办法。再想象一下，玩具鼓和鼓槌分散在玩具箱里，两个小孩同时都想玩。于是，他们翻遍玩具箱，其中一人找到了玩具鼓，另一人找到了鼓槌，除非当中一位割爱让对方先玩，否则，他们只会僵持不下，各自都紧抓手中的部件不放，还要求对方“缴械”，结果都玩不成。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "现在进行类比，我们面对的并非小孩争抢玩具，而是线程在互斥上争抢锁：有两个线程，都需要同时锁住两个互斥，才可以进行某项操作，但它们分别都只锁住了一个互斥，都等着再给另一个互斥加锁。于是，双方毫无进展，因为它们同在苦苦等待对方解锁互斥。上述情形称为**死锁（deadlock）**。为了进行某项操作而对多个互斥加锁，由此诱发的最大的问题之一正是死锁。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "防范死锁的建议通常是，始终按相同顺序对两个互斥加锁。若我们总是先锁互斥 A再锁互斥 B，则永远不会发生死锁。有时候，这直观、易懂，因为诸多互斥的用途各异。但也会出现棘手的状况，例如，运用多个互斥分别保护多个独立的实例，这些实例属于同一个类。考虑一个函数，其操作同一个类的两个实例，互相交换它们的内部数据。为了保证互换正确完成，免受并发改动的不良影响，两个实例上的互斥都必须加锁。可是，如果选用了固定的次序（两个对象通过参数传入，我们总是先给第一个实例的互斥加锁，再轮到第二个实例的互斥），前面的建议就适得其反：针对两个相同的实例，若两个线程都通过该函数在它们之间互换数据，只是两次调用的参数顺序相反(译者注：即线程甲调用 `swap(A, B)`，线程乙调用 `swap(B, A)`。请注意，这里重复进行互换操作，并不符合逻辑，因为会使两个实例最终保持原样。本例意在描述发生死锁的情形，但重复操作本身不具备现实意义。)，会导致它们陷入死锁！"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "所幸，C++标准库提供了 `std::lock()`函数，专门解决这一问题。它可以同时锁住多个互斥，而没有发生死锁的风险。\n",
    "\n",
    "代码清单 3.6 给出了示范代码，在简单的内部数据互换操作中运用 `std::lock()`函数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// 代码清单 3.6 运用 std::lock()函数和 std::lock_guard<>类模板，进行内部数据的互换操作\n",
    "\n",
    "#include <mutex>\n",
    "\n",
    "class some_big_object {};\n",
    "\n",
    "void swap(some_big_object& lhs, some_big_object& rhs) {}\n",
    "\n",
    "class X {\n",
    "   private:\n",
    "    some_big_object some_detail;\n",
    "    mutable std::mutex m;\n",
    "\n",
    "   public:\n",
    "    X(some_big_object const& sd) : some_detail(sd) {}\n",
    "\n",
    "    friend void swap(X& lhs, X& rhs) {\n",
    "        if (&lhs == &rhs) return;\n",
    "        std::lock(lhs.m, rhs.m); // 1\n",
    "        std::lock_guard<std::mutex> lock_a(lhs.m, std::adopt_lock); // 2\n",
    "        std::lock_guard<std::mutex> lock_b(rhs.m, std::adopt_lock); // 3\n",
    "        swap(lhs.some_detail, rhs.some_detail);\n",
    "    }\n",
    "};\n",
    "\n",
    "int main() {}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "本例的函数一开始就对比两个参数，以确定它们指向不同实例。此项判断必不可少，原因是，若我们已经在某个 `std::mutex` 对象上获取锁，那么再次试图从该互斥获取锁将导致未定义行为（`std::recursive_mutex`类型的互斥准许同一线程重复加锁，详见3.3.3节）。\n",
    "\n",
    "接着，代码调用 `std::lock()`锁定两个互斥①，并依据它们分别构造 `std::lock_guard` 实例②③。我们除了用互斥充当这两个实例的构造参数，还额外提供了 `std::adopt_lock` 对象，以指明互斥已被锁住，即互斥上有锁存在，`std::lock_guard` 实例应当据此接收锁的归属权，不得在构造函数内试图另行加锁。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "无论函数是正常返回，还是因受保护的操作抛出异常而导致退出，`std::lock_guard`都保证了互斥全都正确解锁。另外，值得注意的是，`std::lock()`在其内部对 `lhs.m` 或 `rhs.m`加锁，这一函数调用可能导致抛出异常，这样，异常便会从 `std::lock()`向外传播。假如`std::lock()`函数在其中一个互斥上成功获取了锁，但它试图在另一个互斥上获取锁时却有异常抛出，那么第一个锁就会自动释放：若加锁操作涉及多个互斥，则 `std::lock()`函数的语义是“全员共同成败”（all-or-nothing，或全部成功锁定，或没获取任何锁并抛出异常）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "针对上述场景，C++17 还进一步提供了新的 RAII 类模板 `std::scoped_lock<>`。`std::scoped_lock<>`和 `std::lock_guard<>`完全等价，只不过前者是可变参数模板（variadic template），接收各种互斥型别作为模板参数列表，还以多个互斥对象作为构造函数的参数列表。\n",
    "\n",
    "下列代码中，传入构造函数的两个互斥都被加锁，机制与 `std::lock()`函数相同，因此，当构造函数完成时，它们就都被锁定，而后，在析构函数内一起被解锁。我们可以重写代码清单 3.6 的 `swap()`函数，其内部操作代码如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "void swap(X& lhs, X& rhs) {\n",
    "  if (&lhs == &rhs) return;\n",
    "  std::scoped_lock guard(lhs.m, rhs.m); // 1\n",
    "  swap(lhs.some_detail, rhs.some_detail);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上例利用了 C++17 加入的另一个新特性：类模板参数推导。假使读者的编译器支持C++17 标准（通过查验能否使用 `std::scoped_lock` 即可判断，因为它是 C++17 程序库工具），C++17 具有隐式类模板参数推导（implicit class template parameter deduction）机制，依据传入构造函数的参数对象自动匹配①，选择正确的互斥型别。\n",
    "\n",
    "①处的语句等价于下面完整写明的版本："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "std::scoped_lock<std::mutex,std::mutex> guard(lhs.m, rhs.m); "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在 C++17 之前，我们采用 `std::lock()`编写代码。现在有了 `std::scoped_lock`，于是那些代码绝大多数可以改用这个编写，从而降低出错的概率。这肯定是件好事！"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "假定我们需要同时获取多个锁，那么 `std::lock()`函数和 `std::scoped_lock<>`模板即可帮助防范死锁；*但若代码分别获取各个锁*，它们就鞭长莫及了。\n",
    "\n",
    "在这种情况下，我们身为开发人员，唯有依靠经验力求防范死锁。知易行难，死锁是最棘手的多线程代码问题之一，绝大多数情形中，纵然一切都运作正常，死锁也往往无法预测。尽管如此，我们编写的代码只要服从一些相对简单的规则，便有助于防范死锁。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 防范死锁的补充准则"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "虽然死锁的最常见诱因之一是锁操作，但即使没有牵涉锁，也会发生死锁现象。\n",
    "\n",
    "假定有两个线程，各自关联了 `std::thread` 实例，若它们同时在对方的 `std::thread` 实例上调用 `join()`，就能制造出死锁现象却不涉及锁操作。这种情形与前文的小孩争抢玩具相似，两个线程都因苦等对方结束而停滞不前。如果线程甲正等待线程乙完成某一动作，同时线程乙却在等待线程甲完成某一动作，便会构成简单的循环等待，并且线程数目不限于两个：就算是 3 个或更多线程，照样会引起死锁。\n",
    "\n",
    "防范死锁的准则最终可归纳成一个思想：只要另一线程有可能正在等待当前线程，那么当前线程千万不能反过来等待它。\n",
    "\n",
    "下列准则的细分条目给出了各种方法，用于判别和排除其他线程是否正在等待当前线程。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1．避免嵌套锁"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "第一条准则最简单：假如已经持有锁，就不要试图获取第二个锁。若能恪守这点，每个线程便最多只能持有唯一一个锁，仅锁的使用本身不可能导致死锁。但是还存在其他可能引起死锁的场景（譬如，多个线程彼此等待），而操作多个互斥锁很可能就是最常见的死锁诱因。万一确有需要获取多个锁，我们应采用 `std::lock()`函数，借单独的调用动作一次获取全部锁来避免死锁。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2．一旦持锁，就须避免调用由用户提供的程序接口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这是上一条准则的延伸。若程序接口由用户自行实现，则我们无从得知它到底会做什么，它可能会随意操作，包括试图获取锁。一旦我们已经持锁，若再调用由用户提供的程序接口，而它恰好也要获取锁，那便违反了避免嵌套锁的准则，可能发生死锁。不过，有时这实在难以避免。对于类似 3.2.3 节的栈容器的泛型代码，只要其操作与模板参数的型别有关，它就不得不依赖用户提供的程序接口。因此我们需要另一条新的准则。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3．依从固定顺序获取锁"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果多个锁是绝对必要的，却无法通过 `std::lock()`在一步操作中全部获取，我们只能退而求其次，在每个线程内部都依从固定顺序获取这些锁。\n",
    "\n",
    "我们在 3.2.4 节已经提及，若在两个互斥上获取锁，则有办法防范死锁：关键是，事先规定好加锁顺序，令所有线程都依从。这在一些情况下相对简单、易行。以 3.2.3 节的栈容器为例，互斥在栈容器的实例内部发挥作用，但假如操作涉及栈容器存放的元素，就须调用由用户提供的接口。然而我们也可以约束栈容器内存储的元素：任何针对元素所执行的操作，均不得牵扯到栈容器本身。该限制给栈容器的使用者造成了负担。不过，栈容器中存储的元素极少会访问栈容器本身，万一发生访问，我们也能明显觉察，故这种负担并非难以承受。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "另外几种情况很直观，如 3.2.4 节的互换操作。虽然这种方式并不一定总是可行，但在该情况下，我们至少可以同时对两个互斥加锁。回顾 3.1 节所介绍的双向链表，便能发现一种可行的方法：给每个节点都配备互斥来保护链表。因此，线程为了访问链表，须对涉及的每个节点加锁。就执行删除操作的线程而言，它必须在 3 个节点上获取锁，即要被删除的目标节点和两侧的相邻节点，因为它们全都会在不同程度上被改动。类似地，若要遍历链表，线程必须持有当前节点的锁，同时在后续节点上获取锁，从而确保前向指针不被改动。一旦获取了后续节点上的锁，当前节点的锁便再无必要，遂可释放。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上述加锁方式很像步行过程中双腿交替迈进。按照这种方式，链表容许多个线程一起访问，前提是它们不会同时访问同一个节点。不过，节点必须依从相同的锁定顺序以预防死锁：假如两个线程从相反方向遍历链表，并采用交替前进的加锁方式，它们就会在途中互相死锁。假定 A 和 B 是链表中的两个相邻节点，正向遍历的线程会先尝试持有节点 A 的锁，接着再从节点 B 上获取锁。逆向遍历的线程则持有节点 B 的锁，并试图从节点 A 上获取锁，这会导致出现经典场景，发生死锁！如图 3.2 所示。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 图 3.2 两个线程从相反方向遍历链表\n",
    "\n",
    "| 线程甲 | 线程乙 |\n",
    "|-------|-------|\n",
    "| 锁住链表的全局入口的互斥 | |\n",
    "| 通过`head`指针读取头节点 | |\n",
    "| 锁住头节点的互斥 | |\n",
    "| 解锁链表的全局入口的互斥 | |\n",
    "| | 锁住链表的全局入口的互斥 |\n",
    "| | 通过`tail`指针读取尾节点 |\n",
    "| 读取`head->next`指针 | 锁住尾节点的互斥 |\n",
    "| 锁定`next`节点的互斥 | 读取`tail->prev`指针 |\n",
    "| 读取`next->next`指针 | 解锁尾节点的互斥 |\n",
    "| ... | ... |\n",
    "| 锁住节点A的互斥 | 锁住节点C的互斥 |\n",
    "| 读取`A->next`指针（指向B节点） | 读取`C->prev`指针（指向B节点） |\n",
    "| | 锁住节点B的互斥 |\n",
    "| 试图锁住节点B的互斥，发生阻塞 | 解锁节点C的互斥 |\n",
    "| | 读取`B->prev`指针（指向A节点） |\n",
    "| | 试图锁住节点A的互斥，发生阻塞 |\n",
    "| 死锁！ | |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "类似地，假设节点 B 位于节点 A 和 C 之间，若线程甲要删除 B，便先在 B 上获取锁，然后再锁住 A 和 C。如果线程乙正同时遍历链表，则可能会先锁住 A 或 C（具体锁住哪个，取决于遍历方向），却随即发现无法在节点 B 上获取锁，因线程甲已经持有 B的锁，并尝试在 A 或 C 上获取锁。遂甲、乙线程互相死锁。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "此处有一个方法可防范死锁：规定遍历的方向。从而令线程总是必须先锁住 A，再锁住 B，最后锁住 C。这样，我们就可以以禁止逆向遍历为代价而防范可能的死锁。其他数据结构也会设定相似的准则。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4．按层级加锁"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "锁的层级划分就是按特定方式规定加锁次序，在运行期据此查验加锁操作是否遵从预设规则。按照构思，我们把应用程序分层，并且明确每个互斥位于哪个层级。若某线程已对低层级互斥加锁，则不准它再对高层级互斥加锁。具体做法是将层级的编号赋予对应层级应用程序上的互斥，并记录各线程分别锁定了哪些互斥。这种模式虽然常见，但C++标准库尚未提供直接支持，故我们需自行编写定制的互斥型别`hierarchical_mutex`，如代码清单 3.7 所示。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// https://godbolt.org/z/9jj59TYnv\n",
    "// 代码清单 3.7 举例示范了两个线程如何运用层级互斥。\n",
    "\n",
    "#include <mutex>\n",
    "\n",
    "class hierarchical_mutex {\n",
    "   public:\n",
    "    explicit hierarchical_mutex(unsigned level) {}\n",
    "\n",
    "    void lock() {}\n",
    "    void unlock() {}\n",
    "};\n",
    "\n",
    "hierarchical_mutex high_level_mutex(10000); // 1\n",
    "hierarchical_mutex low_level_mutex(5000);   // 2\n",
    "\n",
    "int do_low_level_stuff() { return 42; }\n",
    "\n",
    "int low_level_func() {\n",
    "    std::lock_guard<hierarchical_mutex> lk(low_level_mutex); // 4\n",
    "    return do_low_level_stuff();\n",
    "}\n",
    "\n",
    "void high_level_stuff(int some_param) {}\n",
    "\n",
    "void high_level_func() {\n",
    "    std::lock_guard<hierarchical_mutex> lk(high_level_mutex); // 6\n",
    "    high_level_stuff(low_level_func()); // 5\n",
    "}\n",
    "\n",
    "void thread_a() { high_level_func(); }\n",
    "\n",
    "hierarchical_mutex other_mutex(6000); // hierarchical_mutex other_mutex(100); 3\n",
    "void do_other_stuff() {}\n",
    "\n",
    "void other_stuff() {\n",
    "    high_level_func(); // 10\n",
    "    do_other_stuff();\n",
    "}\n",
    "\n",
    "void thread_b() { // 8\n",
    "    std::lock_guard<hierarchical_mutex> lk(other_mutex); // 9\n",
    "    other_stuff();\n",
    "}\n",
    "\n",
    "int main() {}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "代码清单 3.7 中含有 3 个 `hierarchical_mutex` 实例①②③，它们依据相应的层级编号而构造（层级越低编号越小）。这套机制旨在设定加锁的规则，如果我们已在某`hierarchical_mutex` 互斥上持有锁，那么只能由相对低层级的 h`ierarchical_mutex` 互斥获取锁，从而限制代码的行为。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们在这里假定，`do_low_level_stuff()`函数没有锁住任何互斥，而 `low_level_func()`函数处于最低层级④，且锁住了互斥 `low_level_mutex。high_level_func()`函数先对互斥`high_level_mutex` 加锁⑥，随后调用 `low_level_func()`⑤，这两步操作符合加锁规则，因为互斥 `high_level_mutex`①所在的层级（10000）高于 `low_level_mutex`②所在的层级（5000）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`thread_a()`同样遵循规则⑦，所以运行无碍。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "相反地，`thread_b()`无视规则⑧，\n",
    "\n",
    "因此在运行期出错。它先对互斥 `other_mutex` 加锁⑨，其层级编号是 6000③，说明该互斥位于中间层级。在 `other_stuff()`函数调用`high_level_func()`⑩之时，就违反了层级规则：`high_level_func()`试图在互斥 `high_level_mutex` 上获取锁，但其层级编号却是 10000，远高于当前层级编号 6000。结果，互斥`hierarchical_mutex` 会报错，可能抛出异常，也可能中止程序。层级互斥之间不可能发生死锁，因为互斥自身已经被强制限定了加锁次序。只要两个层级锁都位于相同层级，我们便无法一并持有。若将层级锁应用于前文交替前进的加锁策略，那么链表中每个互斥的层级须低于其前驱节点互斥的层级。可是，这种方式在某些情况下并不可行。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "代码清单 3.7 还展示了另一点：依据用户自定义的互斥型别，将类模板 `std::lock_ guard<>`具体化。`hierarchical_mutex` 类并非标准的一部分，但不难编写；代码清单 3.8 给出了简单实现。尽管它属于用户自定义的型别，但也能与 `std::lock_guard<>`结合使用，因其实现了 3 个成员函数—`lock()`、`unlock()`和 `try_lock()`，满足了互斥概念所需具备的操作。我们还没介绍如何使用 `try_lock()`，但它相当简单：若另一线程已在目标互斥上持有锁，则函数立即返回 `false`，完全不等待。`std::lock()`也可在内部利用该函数，实现防范死锁的算法。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "为了存储当前层级编号，`hierarchical_mutex` 的实现使用了线程专属的局部变量。所有互斥的实例都能读取该变量，但它的值因不同线程而异。这使代码可以独立检测各线程的行为，各互斥都能判断是否允许当前线程对其加锁。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// https://godbolt.org/z/do87KTKoG\n",
    "// 代码清单 3.8 简单的层级互斥\n",
    "\n",
    "#include <mutex>\n",
    "#include <stdexcept>\n",
    "#include <climits>\n",
    "\n",
    "class hierarchical_mutex\n",
    "{\n",
    "    std::mutex internal_mutex;\n",
    "    unsigned long const hierarchy_value;\n",
    "    unsigned long previous_hierarchy_value;\n",
    "    static thread_local unsigned long this_thread_hierarchy_value;\n",
    "\n",
    "    void check_for_hierarchy_violation()\n",
    "    {\n",
    "        if(this_thread_hierarchy_value <= hierarchy_value)\n",
    "        {\n",
    "            throw std::logic_error(\"mutex hierarchy violated\");\n",
    "        }\n",
    "    }\n",
    "    void update_hierarchy_value()\n",
    "    {\n",
    "        previous_hierarchy_value=this_thread_hierarchy_value;\n",
    "        this_thread_hierarchy_value=hierarchy_value;\n",
    "    }\n",
    "\n",
    "public:\n",
    "    explicit hierarchical_mutex(unsigned long value):\n",
    "        hierarchy_value(value),\n",
    "        previous_hierarchy_value(0)\n",
    "    {}\n",
    "    void lock()\n",
    "    {\n",
    "        check_for_hierarchy_violation();\n",
    "        internal_mutex.lock();\n",
    "        update_hierarchy_value();\n",
    "    }\n",
    "    void unlock()\n",
    "    {\n",
    "        this_thread_hierarchy_value=previous_hierarchy_value;\n",
    "        internal_mutex.unlock();\n",
    "    }\n",
    "    bool try_lock()\n",
    "    {\n",
    "        check_for_hierarchy_violation();\n",
    "        if(!internal_mutex.try_lock())\n",
    "            return false;\n",
    "        update_hierarchy_value();\n",
    "        return true;\n",
    "    }\n",
    "};\n",
    "\n",
    "thread_local unsigned long\n",
    "    hierarchical_mutex::this_thread_hierarchy_value(ULONG_MAX);\n",
    "\n",
    "int main()\n",
    "{\n",
    "    hierarchical_mutex m1(42);\n",
    "    hierarchical_mutex m2(2000);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这里的关键是，使用线程专属的变量（名为 `this_thread_hierarchy_value`，以关键字`thread_local` 修饰）表示当前线程的层级编号①(线程自身不属于任何层级。`this_thread_hierarchy_value` 的准确意义是，当前线程最后一次加锁操作所牵涉的层级编号)。它初始化为 `unsigned long` 可表示的最大值⑧。故此，最开始，任意 `hierarchical_mutex` 互斥都能被加锁。因为声明由 `thread_local`修饰，每个线程都具有自己的 `this_thread_hierarchy_value` 副本，所以该变量在某线程上的值与另一线程上的值完全无关。关键字 t`hread_local` 的详情请见附录 A.8 节。\n",
    "\n",
    "某线程第一次锁住 `hierarchical_mutex` 的某个实例时，变量 `this_thread_hierarchy_value` 的值是 `ULONG_MAX`。根据定义，它大于任何其他值，因而 `check_for_hierarchy_violation()`的检查顺利通过②。检查完成后，`lock()`委托内部的互斥加锁④。只要成功锁定，层级编号即能更新⑤。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "假设我们已持有互斥 `hierarchical_mutex` 的锁，那么 `this_thread_hierarchy_value` 的值反映出前者所在层级的编号，若要再对另一互斥加锁，后面互斥的层级必须低于前面已被锁定的互斥的层级，才可以通过检查②。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "现在到了重要的步骤：记录当前线程的层级编号，将其保存为“上一次加锁的层级”③。及后，执行 `unlock()`时，线程的层级按保存的值复原⑥；否则，我们就无法重新锁定层级较高的互斥，即使当前线程不再持有任何锁。只有锁定内部互斥`internal_mutex` 之后，我们才着手保存“上一次加锁的层级”③，而在内部互斥解锁之前，复原已经完成⑥，因此内部互斥的保护很到位，它可以安全地保存在 `hierarchical_ mutex` 内部。为了避免乱序解锁而引发层级混淆，如果我们解锁某个层级的互斥，却发现它不是最后一个被加锁的，就抛出异常⑨。还存在其他可行的机制，但所举范例最为简单。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`try_lock()`与 `lock()`的工作原理相同，差别在于，若调用 `try_lock()`，它对内部互斥`internal_mutex` 加锁失败⑦，也就是说，我们没有成功获取锁。因此，当前线程的层级编号不进行更新，并且函数返回 `false` 而不是 `true`。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "尽管上述检查在运行期发生，但判定结果并不依赖时序，读者请不要特意等待引起死锁的情况发生，它们甚为罕见。另外，在设计流程中，只须按照上例的方法将应用程序分层，并设定互斥的层级，就有助于排除许多可能的死锁的诱因，甚至在编写代码前即可排除。即便读者还没深入以上范例的程度，暂时未能写出可在运行期检查层级的代码，仍然值得进行这种设计练习。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5．将准则推广到锁操作以外"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我在本节开始就提到过，死锁现象并不单单因加锁操作而发生，任何同步机制导致的循环等待都会导致死锁出现。因此也值得为那些情况推广上述准则。\n",
    "\n",
    "譬如，我们应尽可能避免获取嵌套锁；若当前线程持有某个锁，却又同时等待别的线程，这便是坏的情况，因为万一后者恰好也需获取锁，反而只能等该锁被释放才能继续运行。类似地，如果要等待线程，那就值得针对线程规定层级，使得每个线程仅等待层级更低的线程。有一种简单方法可实现这种机制：让同一个函数启动全部线程，且汇合工作也由之负责，3.1.2 节和 3.3 节对此已进行解说。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "只要代码采取了防范死锁的设计，函数 `std::lock()`和类 `std::lock_guard` 即可涵盖大多数简单的锁操作，不过我们有时需要更加灵活。标准库针对一些情况提供了 `std::unique_lock<>`模板。它与 `std::lock_guard<>`一样，也是一个依据互斥作为参数的类模板，并且以 RAII 手法管理锁，不过它更灵活一些。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 运用 `std::unique_lock<>`灵活加锁 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "类模板`std::unique_lock<>`放宽了不变量的成立条件，因此它相较 `std::lock_guard<>`更灵活一些。`std::unique_lock` 对象不一定始终占有与之关联的互斥。\n",
    "\n",
    "首先，其构造函数接收第二个参数(第一个参数即为需要加锁的目标互斥)：我们可以传入 `std::adopt_lock` 实例，借此指明 `std::unique_lock` 对象管理互斥上的锁；也可以传入 `std::defer_lock` 实例，从而使互斥在完成构造时处于无锁状态，等以后有需要时才在 `std::unique_lock` 对象（不是互斥对象）上调用 `lock()`而获取锁，或把 `std::unique_lock` 对象交给 `std::lock()` 函数加锁。只要把 `std::lock_guard` 和`std::adopt_lock`分别改成`std::unique_lock`和`std::defer_lock`①，即可轻松重写代码清单3.6，如代码清单 3.9 所示。\n",
    "\n",
    "两段代码的行数相同且功能等效，仅有一处小差别：`std::unique_lock`占用更多的空间，也比 `std::lock_guard` 略慢。但 `std::unique_lock` 对象可以不占有关联的互斥，具备这份灵活性需要付出代价：需要存储并且更新互斥信息。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// 代码清单 3.9 运用 std::lock()函数和 std::unique_lock<>类模板在对象间互换内部数据\n",
    "\n",
    "#include <mutex>\n",
    "\n",
    "class some_big_object {};\n",
    "\n",
    "void swap(some_big_object& lhs, some_big_object& rhs) {}\n",
    "\n",
    "class X {\n",
    "   private:\n",
    "    some_big_object some_detail;\n",
    "    mutable std::mutex m;\n",
    "\n",
    "   public:\n",
    "    X(some_big_object const& sd) : some_detail(sd) {}\n",
    "\n",
    "    friend void swap(X& lhs, X& rhs) {\n",
    "        if (&lhs == &rhs) return;\n",
    "        std::unique_lock<std::mutex> lock_a(lhs.m, std::defer_lock); // 1. 实例 std::defer_lock 将互斥保留为无锁状态\n",
    "        std::unique_lock<std::mutex> lock_b(rhs.m, std::defer_lock); // 1. 实例 std::defer_lock 将互斥保留为无锁状态\n",
    "        std::lock(lock_a, lock_b); // 到这里才对互斥加锁\n",
    "        swap(lhs.some_detail, rhs.some_detail);\n",
    "    }\n",
    "};\n",
    "\n",
    "int main() {}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "代码清单 3.9 中，因为 `std::unique_lock` 类具有成员函数 `lock()`、`try_lock()`和 `unlock()`，所以它的实例得以传给 `std::lock()`函数②。`std::unique_lock` 实例在底层与目标互斥关联，此互斥也具备这 3 个同名的成员函数，因此上述函数调用转由它们实际执行。`std::unique_lock` 实例还含有一个内部标志，亦随着这些函数的执行而更新，以表明关联的互斥目前是否正被该类的实例占据。这一标志必须存在，作用是保证析构函数正确调用 `unlock()`。假如 `std::unique_lock` 实例的确占据着互斥，则其析构函数必须调用 `unlock()`；若不然，实例并未占据互斥，便绝不能调用 `unlock()`。此标志可以通过调用成员函数 `owns_lock()`查询。不过，若条件允许，最好还是采用 C++17 所提供的变参模板类 `std::scoped_lock`（见 3.2.4 节），除非我们必须采用 `std::unique_lock` 类进行某些操作，如转移锁的归属权。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "读者应该知道上述标志需要占用存储空间。故 `std::unique_lock` 对象的“体积”往往大于 `std::lock_guard` 对象的。并且，由于该标志必须适时更新或检查，因此若采用 `std::unique_lock `替换 `std::lock_guard`，便会导致轻微的性能损失。所以，如果 `std::lock_guard`已经能满足所需，我建议优先采用。话说回来，有一些情形需要更灵活的处理方式，则`std::unique_lock`类更为合适。延时加锁即属此例，前文已有示范。另一种情形是，需要从某作用域转移锁的归属权到其他作用域。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 在不同作用域之间转移互斥归属权"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "因为 `std::unique_lock` 实例不占有与之关联的互斥，所以随着其实例的转移，互斥的归属权可以在多个 `std::unique_lock` 实例之间转移。转移会在某些情况下自动发生，譬如从函数返回实例时，但我们须针对别的情形显式调用 `std::move()`。本质上，这取决于移动数据的来源到底是左值还是右值。若是左值（lvalue，实实在在的变量或指向真实变量的引用），则必须显式转移，以免归属权意外地转移到别处；如果是右值（rvalue，某种形式的临时变量），归属权转移便会自动发生。`std::unique_lock` 属于可移动却不可复制的型别。请读者参阅附录 A.1.1 节以探究移动语义的更多细节。 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "转移有一种用途：准许函数锁定互斥，然后把互斥的归属权转移给函数调用者，好让他在同一个锁的保护下执行其他操作。\n",
    "\n",
    "下面的代码片段就此做了示范：`get_lock()`函数先锁定互斥，接着对数据做前期准备，再将归属权返回给调用者："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "std::unique_lock<std::mutex> get_lock() {\n",
    "    extern std::mutex some_mutex;\n",
    "    std::unique_lock<std::mutex> lk(some_mutex);\n",
    "    prepare_data();\n",
    "    return lk; // 1\n",
    "}\n",
    "\n",
    "void process_data() {\n",
    "    std::unique_lock<std::mutex> lk(get_lock());\n",
    "    do_something();\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "由于锁 `lk` 是 `get_lock()`函数中声明的 `std::unique_lock` 局部变量，因此代码无须调用`std::move()`就能把它直接返回①，编译器会妥善调用移动构造函数。在 `process_data()`的函数定义中，也给出了 `std::unique_lock` 实例，而该函数身为 `get_lock()`的调用者，能直接接受锁的归属权的转移②。至此，前期准备已经完成，数据正确、可靠，可以提供给 `do_something()`进一步操作，而且别的线程无法在 `do_something()`调用期间改动数据。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上述模式通常会在两种情形中使用：互斥加锁的时机取决于程序的当前状态；或者，某函数负责执行加锁操作并返回 `std::unique_lock` 对象，而互斥加锁时机则由传入的参数决定。\n",
    "\n",
    "通道（gate way）类是一种利用锁转移的具体形式，锁的角色是其数据成员，用于保证只有正确加锁才能够访问受保护数据，而不再充当函数的返回值。这样，所有数据必须通过通道（gate way）类访问：若想访问数据，则需先取得通道（gate way）类的实例（由函数调用返回，如上例中的 `get_lock()`），再借它执行加锁操作，然后通过通道（gate way）对象的成员函数才得以访问数据。我们在访问完成后销毁通道（gate way）对象，锁便随之释放，别的线程遂可以重新访问受保护的数据。这类通道（gate way）对象几乎是可移动的（只有这样，函数才有可能向外转移归属权），因此锁对象作为其数据成员也必须是可移动的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`std::unique_lock` 类十分灵活，允许它的实例在被销毁前解锁。其成员函数 `unlock()`负责解锁操作，这与互斥一致。`std::unique_lock` 类与互斥还有一共通之处，两者同样具备一套基本的成员函数用于加锁和解锁，因此该类可以结合泛型函数来使用，如`std::lock()`。`std::unique_lock` 的实例可以在被销毁前解锁。这就意味着，在执行流程的任何特定分支上，若某个锁显然没必要继续持有，我们则可解锁。这对应用程序的性能颇为重要：在所需范围之外持锁将使性能下降，因为如果有其他线程需要加锁，就会被迫毫无必要地延长等待时间，导致运行受阻。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 按适合的粒度加锁*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在 3.2.3 节我们就曾经提过“锁粒度”，该术语描述一个锁所保护的数据量，但它没有严格的实质定义。\n",
    "\n",
    "粒度精细的锁保护少量数据，而粒度粗大的锁保护大量数据。锁操作有两个要点：一是选择足够粗大的锁粒度，确保目标数据受到保护；二是限制范围，务求只在必要的操作过程中持锁。设想我们在超市里往购物车塞满商品，排队等着结账，不巧，前面正在清点结账的顾客突然间意识到，他忘了还要买小红莓果酱，于是全然不顾身后的人而抽身去找；或者，收银员已经要收款了，顾客才匆匆打开手提袋翻找钱包，我们都体会过这种无奈。如果人人都在结账之前备齐想买的商品，并准备好恰当的付款方法，事情就好办得多。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "多线程也适用这个道理：假定多个线程正等待使用同一个资源（如柜台处的收银员），如果任何线程在必要范围以外持锁，就会增加等待所耗费的总时间（别等到快付款了，才开始去找小红莓果酱）。只要条件允许，我们仅仅在访问共享数据期间才锁住互斥，让数据处理尽可能不用锁保护。请特别注意，持锁期间应避免任何耗时的操作，如读写文件。同样是读写总量相等的数据，文件操作通常比内存慢几百倍甚至几千倍。除非锁的本意正是保护文件访问，否则，为 I/O 操作加锁将毫无必要地阻塞其他线程（它们因等待获取锁而被阻塞），即使运用了多线程也无法提升性能。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这种情况可用 `std::unique_lock` 处理：假如代码不再需要访问共享数据，那我们就调用 `unlock()`解锁；若以后需重新访问，则调用 `lock()`加锁。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "void get_and_process_data() {\n",
    "    std::unique_lock<std::mutex> my_lock(the_mutex);\n",
    "    some_class data_to_process = get_next_data_chunk();\n",
    "    my_lock.unlock(); // 1. 假定在调用 process() 期间，互斥无须加锁\n",
    "    result_type result = process(data_to_process);\n",
    "    my_lock.lock(); // 2. 重新锁住互斥，以写出结果\n",
    "    write_result(data_to_process, result);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "假定 `process()`函数全程无须为互斥加锁，那我们应该在调用前手动解锁①，其后重新锁定②。\n",
    "\n",
    "希望读者可以清楚下面的事实：若只用单独一个互斥保护整个数据结构，不但很可能加剧锁的争夺，还将难以缩短持锁时间。假设某项操作需对同一个互斥全程加锁，当中步骤越多，则持锁时间越久。这是一种双重损失，恰恰加倍促使我们尽可能改用粒度精细的锁。\n",
    "\n",
    "上例说明，加锁时选用恰当的粒度，不仅事关锁定数据量的大小，还牵涉持锁时间以及持锁期间能执行什么操作。一般地，若要执行某项操作，那我们应该只在所需的最短时间内持锁。换言之，除非绝对必要，否则不得在持锁期间进行耗时的操作，如等待I/O 完成或获取另一个锁（即便我们知道不会死锁）。\n",
    "\n",
    "在代码清单 3.6 和代码清单 3.9 中，数据互换操作显然必须并发访问两个对象，该操作需锁定两个互斥。设想原本的场景变成：我们试图比较两个简单的数据成员，其型别是 C++的原生 `int`。新、旧场景存在区别吗？存在。因为 `int` 的值复制起来开销甚低，所以程序可以先锁住比较运算的目标对象，从中轻松地复制出各自相关的数据，再用复制的值进行比较运算。这样做的意义是，我们并非先持有一个锁再锁定另一个互斥，而是分别对两个互斥加锁，使得持锁时间最短。代码清单 3.10 实现了上述方式，通过类`Y`示范等值比较运算符。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// 代码清单 3.10 在比较运算的过程中，每次只锁住一个互斥\n",
    "\n",
    "#include <mutex>\n",
    "\n",
    "class Y {\n",
    "   private:\n",
    "    int some_detail;\n",
    "    mutable std::mutex m;\n",
    "\n",
    "    int get_detail() const {\n",
    "        std::lock_guard<std::mutex> lock_a(m); // 1\n",
    "        return some_detail;\n",
    "    }\n",
    "\n",
    "   public:\n",
    "    Y(int sd) : some_detail(sd) {}\n",
    "\n",
    "    friend bool operator==(Y const& lhs, Y const& rhs) {\n",
    "        if (&lhs == &rhs) return true;\n",
    "        int const lhs_value = lhs.get_detail(); // 2\n",
    "        int const rhs_value = rhs.get_detail(); // 3\n",
    "        return lhs_value == rhs_value; // 4\n",
    "    }\n",
    "};\n",
    "\n",
    "int main() {}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "本例中，比较运算符首先调用成员函数 `get_detail()`，以获取需要比较的值②③。该函数先加锁保护数据①，再取值。接着，比较运算符对比取得的值④。新场景下，为了缩短持锁定的时间，我们一次只持有一个锁（这也排除了死锁的可能），而原本的场景则将两个对象一起锁定。请注意，新场景中隐秘地篡改了比较运算的原有语义。在代码清单 3.10 中，若比较运算符返回 `true`，则其意义是：`lhs.some_detail` 在某时刻的值等于`rhs.some_detail` 在另一时刻的值。在两次获取之间②③，它们的值有可能已经以任意形式发生变化，令比较运算失去意义。例如，尽管事实上两者在任何时刻都不相等，但在上述过程中双方发生了互换，最终令比较运算结果为 `true`，错误地表明它们等值。因而做这种改动时必须保持谨慎，免得运算语义遭到篡改而产生问题：若我们未能持有必要的锁以完全保护整个运算，便会将自己置身于条件竞争的危险中。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "有时候，数据结构的各种访问须采取不同层级的保护，但固定级别的粒度并不适合。`std::mutex` 功能平实，无法面面俱到，故改用其他保护方式可能更恰当。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3.3 保护共享数据的其他工具"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "虽然互斥是保护共享数据的最普遍的方式之一，但它并非唯一方式。针对具体场景，还有别的方式可以提供更适合的保护措施。\n",
    "\n",
    "一种格外极端却特别常见的情况是，为了并发访问，共享数据仅需在初始化过程中受到保护，之后再也无须进行显式的同步操作。这可能是因为共享数据一旦创建就处于只读状态，原本可能发生的同步问题遂不复存在；也可能是因为后续操作已为共享数据施加了必要的隐式保护。无论在哪种情况中，若加锁是单纯为了保护共享数据初始化，但完成初始化后却继续锁住互斥，那就成了画蛇添足，还会造成不必要的性能损失。鉴于此，C++标准提供了一套机制，仅为了在初始化过程中保护共享数据。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 在初始化过程中保护共享数据*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "假设我们需要某个共享数据，而它创建起来开销不菲。因为创建它可能需要建立数据库连接或分配大量内存，所以等到必要时才真正着手创建。这种方式称为延迟初始化（lazy initialization），常见于单线程代码。对于需要利用共享资源的每一项操作，要先在执行前判别该数据是否已经初始化，若没有，则及时初始化，然后方可使用。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "std::shared_ptr<some_resource> resource_ptr;\n",
    "\n",
    "void foo() {\n",
    "    if (!resource_ptr) {\n",
    "        resource_ptr.reset(new some_resource); // 1\n",
    "    }\n",
    "    resource_ptr->do_something();\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "假定共享数据本身就能安全地被并发访问，若将上面的代码转化成多线程形式，则仅有初始化过程需要保护①。代码清单 3.11 是采用精简方式改写的，不过，如果数据为多个线程所用，那么它们便无法被并发访问，线程只能毫无必要地循序运行，因为每个线程都必须在互斥上轮候，等待查验数据是否已经完成初始化。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// 代码清单 3.11 用互斥实现线程安全的延迟初始化\n",
    "\n",
    "#include <memory>\n",
    "#include <mutex>\n",
    "\n",
    "struct some_resource {\n",
    "    void do_something() {}\n",
    "};\n",
    "\n",
    "std::shared_ptr<some_resource> resource_ptr;\n",
    "std::mutex resource_mutex;\n",
    "void foo() {\n",
    "    std::unique_lock<std::mutex> lk(resource_mutex); // 1. 此处，全部线程都被迫循序运行\n",
    "    if (!resource_ptr) {\n",
    "        resource_ptr.reset(new some_resource); // 2. 仅有初始化需要保护\n",
    "    }\n",
    "    lk.unlock();\n",
    "    resource_ptr->do_something();\n",
    "}\n",
    "\n",
    "int main() { foo(); }"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面的代码模式司空见惯，但它毫无必要地迫使多个线程循序运行，很有问题。\n",
    "\n",
    "为此，许多人尝试改进，包括实现倍受诟病的*双重检验锁定模式*（double-checked locking pattern）。\n",
    "- 首先，在无锁条件下读取指针①，只有读到空指针才获取锁。\n",
    "- 其次，当前线程先判 空指针①，随即加锁。\n",
    "\n",
    "两步操作之间存在间隙，其他线程或许正好借机完成初始別化。我们需再次检验空指针②（双重检验），以防范这种情形发生："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "void undefined_behaviour_with_double_checked_locking() {\n",
    "    if (!resource_ptr) { // 1\n",
    "        std::lock_guard<std::mutex> lk(resource_mutex);\n",
    "        if (!resource_ptr) { // 2\n",
    "            resource_ptr.reset(new some_resource); // 3\n",
    "        }\n",
    "    }\n",
    "    resource_ptr->do_something(); // 4\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "很遗憾，这种新的模式饱受诟病，因为它有可能诱发恶性条件竞争，问题的根源是：当前线程在锁保护范围外读取指针①，而对方线程却可能先获取锁，顺利进入锁保护范围内执行写操作③，因此读写操作没有同步，产生了条件竞争，既涉及指针本身，还涉及其指向的对象。尽管当前线程能够看见其他线程写入指针，却有可能无视新实例`some_resource` 的创建(1)，结果 `do_something()`的调用就会对不正确的值进行操作④。\n",
    "\n",
    "C++标准将此例定义为数据竞争（data race），是条件竞争的一种，其将导致未定义行为，所以我们肯定要防范。第 5 章将详细讨论内存模型，分析数据竞争形成的前因后果，读者可先参考。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> (AI和知乎有回答这个译者注是错误的) ~~译者注：具体过程如下。在 `undefined_behaviour_with_double_checked_locking()`函数的代码中，最初指针为空，当前线程和对方线程均进入第一层 `if` 分支①。接着对方线程夺得锁 `lk`，顺利进入第二层`if` 分支②；当前线程则被阻塞，在①②之间等待。然后对方线程一气呵成执行完余下全部代码：创建新实例并令指针指向它③，继而离开 `if` 分支，锁 `lk` 随之被销毁，最终调用 `do_something()`操作新实例，更改其初始值④。当前线程后来终于获得了锁，便继续运行：这时它发现指针非空②，遂转去执行 `do_something()`④，但实例已被改动过而当前线程却不知情，于是仍按其初值操作，错误发生。~~\n",
    "\n",
    "| 步骤 | 线程1 | 线程2 | 说明 |\n",
    "|------|-------|-------|------|\n",
    "| 1 | 检查 `resource_ptr` 是否为空(语句1) | - | 假设此时 `resource_ptr` 为空 |\n",
    "| 2 | 获取互斥锁 | - | 线程1成功获取锁 |\n",
    "| 3 | 再次检查 `resource_ptr` 是否为空(语句2) | - | 确认为空 |\n",
    "| 4 | 开始创建资源对象(语句3) | - | `new some_resource` 操作可能包含三个步骤:<br>1. 分配内存<br>2. 构造对象<br>3. 将地址赋给 `resource_ptr` |\n",
    "| 5 | 分配内存 | - | 为对象分配内存空间 |\n",
    "| 6 | 开始构造对象 | - | 开始调用构造函数 |\n",
    "| 7 | - | 检查 `resource_ptr` 是否为空(语句1) | **问题出现**：由于编译器优化或内存模型问题，线程2可能看到非空的 `resource_ptr`，尽管对象构造尚未完成 |\n",
    "| 8 | 继续构造对象 | 看到非空指针，跳过锁定部分 | 线程2认为资源已经完全初始化 |\n",
    "| 9 | - | 尝试使用资源(语句4) | **未定义行为**：线程2访问未完全初始化的对象 |\n",
    "| 10 | 完成对象构造 | - | 线程1完成构造，但为时已晚 |\n",
    "| 11 | 释放互斥锁 | - | 线程1完成初始化步骤 |\n",
    "| 12 | 使用资源(语句4) | - | 线程1正常使用资源 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "C++标准委员会相当重视以上情况，在 C++标准库中提供了 `std::once_flag` 类和 `std:: call_once()`函数，以专门处理该情况。\n",
    "\n",
    "上述代码先锁住互斥，再显式检查指针，导致问题出现。我们对症下药，令所有线程共同调用 `std::call_once()`函数，从而确保在该调用返回时， 指针初始化由其中某线程安全且唯一地完成（通过适合的同步机制）。必要的同步数据则由 `std::once_flag` 实例存储，每个 `std::once_flag` 实例对应一次不同的初始化。相比显式使用互斥，`std::call_once()`函数的额外开销往往更低，特别是在初始化已经完成的情况下，所以如果功能符合需求就应优先使用。运用 `std::call_once()`重写代码清单 3.11即得出下面的代码，两者均实现了相同的操作。下面的代码中，初始化通过函数调用完成，不过只要一个类具备函数调用操作符，则该类的实例也可以轻松地通过这种方式进行初始化。标准库中的一些函数接收函数或断言(2)作为参数，`std::call_once()`与它们当中的大多数相似，能与任何函数或可调用对象配合工作："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 译者注：断言即 predicate，又称“谓词”。在 C++语境下，它是函数或可调用对象，返回布尔值，专门用于判断某条件是否成立。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "std::shared_ptr<some_resource> resource_ptr;\n",
    "std::once_flag resource_flag; // 1\n",
    "\n",
    "void init_resource() { resource_ptr.reset(new some_resource); }\n",
    "\n",
    "void foo() {\n",
    "    std::call_once(resource_flag, init_resource); // 2. 初始化函数准确地被唯一一次调用\n",
    "    resource_ptr->do_something();\n",
    "}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上例包含两个对象，需要初始化的数据(1)和 `std::once_flag` 对象①，两者的作用域都完整涵盖它们所属的名字空间。不过，就算是某个类的数据成员，我们依然能方便地实施延迟初始化，如代码清单 3.12 所示。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> (1) 该数据的类型为 `some_resource`，由共享指针 `resource_ptr` 指向"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// 代码清单 3.12 利用 std::call_once()函数对类 X 的数据成员实施线程安全的延迟初始化\n",
    "\n",
    "#include <mutex>\n",
    "\n",
    "struct connection_info {};\n",
    "\n",
    "struct data_packet {};\n",
    "\n",
    "struct connection_handle {\n",
    "    void send_data(data_packet const&) {}\n",
    "    data_packet receive_data() { return data_packet(); }\n",
    "};\n",
    "\n",
    "struct remote_connection_manager {\n",
    "    connection_handle open(connection_info const&) {\n",
    "        return connection_handle();\n",
    "    }\n",
    "} connection_manager;\n",
    "\n",
    "class X {\n",
    "   private:\n",
    "    connection_info connection_details;\n",
    "    connection_handle connection;\n",
    "    std::once_flag connection_init_flag;\n",
    "\n",
    "    void open_connection() {\n",
    "        connection = connection_manager.open(connection_details);\n",
    "    }\n",
    "\n",
    "   public:\n",
    "    X(connection_info const& connection_details_)\n",
    "        : connection_details(connection_details_) {}\n",
    "    void send_data(data_packet const& data) { // 1\n",
    "        std::call_once(connection_init_flag, &X::open_connection, this); // 2\n",
    "        connection.send_data(data);\n",
    "    }\n",
    "    data_packet receive_data() { // 3\n",
    "        std::call_once(connection_init_flag, &X::open_connection, this);\n",
    "        return connection.receive_data();\n",
    "    }\n",
    "};\n",
    "\n",
    "int main() {}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "代码清单 3.12 中的初始化或在 `send_data()`的首次调用中进行①，或在 `receive_data()`的第一次调用中进行③。它们都借助成员函数 `open_connection()`初始化数据，而该函数必须用到 `this` 指针，所以要向其传入 `this` 指针。标准库的某些函数接收可调用对象，如`std::thread `的构造函数和 `std::bind()`函数，`std::call_once()`同样如此，故本例代码也向它传递 `this` 指针作为附加参数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "值得一提的是，`std::once_flag` 的实例既不可复制也不可移动，这与 `std::mutex` 类似。若像上例那样让它充当类的数据成员，而涉及初始化的两个成员函数功能特殊，则这些数据经由它们调用 `call_once()`才可以进行操作，所以这两个函数必须显式定义。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果把局部变量声明成静态数据，那样便有可能让初始化过程出现条件竞争。\n",
    "\n",
    "根据C++标准规定，只要控制流程第一次遇到静态数据的声明语句，变量即进行初始化。若多个线程同时调用同一函数，而它含有静态数据，则任意线程均可能首先到达其声明处，这就形成了条件竞争的隐患。\n",
    "\n",
    "C++11 标准发布之前，许多编译器都未能在实践中正确处理该条件竞争。其原因有可能是众多线程均认定自己是第一个，都试图初始化变量；也有可能是某线程上正在进行变量的初始化，但尚未完成，而别的线程却试图使用它。C++11 解决了这个问题，规定初始化只会在某一线程上单独发生，在初始化完成之前，其他线程不会越过静态数据的声明而继续运行。于是，这使得条件竞争原来导致的问题变为，初始化应当由哪个线程具体执行。某些类的代码只需用到唯一一个全局实例，这种情形可用以下方法代替 `std::call_once()`："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "class my_class; \n",
    "\n",
    "my_class& get_my_class_instance() { // 线程安全的初始化，C++11标准保证其正确性\n",
    "    static my_class instance;  \n",
    "    return instance; \n",
    "} "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "多个线程可以安全地调用 `get_my_class_instance()`①，而无须担忧初始化的条件竞争。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "仅在初始化过程中保护共享数据只是一种特例，更普遍的情况是保护那些甚少更新的数据结构。大多数时候，这些数据结构都处于只读状态，因此可被多个线程并发访问，但它们偶尔也需要更新。我们需要一种保护机制专门处理这种场景。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// https://godbolt.org/z/q31GEE8d7\n",
    "\n",
    "#include <iostream>\n",
    "\n",
    "void initializeStatic() {\n",
    "    static int value = []() {\n",
    "        std::cout << \"Static variable initialized\" << std::endl;\n",
    "        return 42;\n",
    "    }();\n",
    "    std::cout << \"Value: \" << value << std::endl;\n",
    "}\n",
    "\n",
    "int main() {\n",
    "    initializeStatic(); // 第一次调用，初始化静态变量\n",
    "    initializeStatic(); // 第二次调用，跳过初始化\n",
    "    return 0;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// https://godbolt.org/z/z5bTzbMGP\n",
    "#include <iostream>\n",
    "#include <thread>\n",
    "#include <mutex>\n",
    "\n",
    "std::once_flag flag;\n",
    "\n",
    "void initializeOnce() {\n",
    "    std::call_once(flag, []() {\n",
    "        std::cout << \"Call once executed\" << std::endl;\n",
    "    });\n",
    "    std::cout << \"Function called\" << std::endl;\n",
    "}\n",
    "\n",
    "int main() {\n",
    "    std::thread t1(initializeOnce);\n",
    "    std::thread t2(initializeOnce);\n",
    "\n",
    "    t1.join();\n",
    "    t2.join();\n",
    "\n",
    "    return 0;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 保护甚少更新的数据结构 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "考虑一个存储着 DNS 条目的缓存表，它将域名解释成对应的 IP 地址。给定的 DNS条目通常在很长时间内都不会变化—在许多情况下，DNS 条目保持多年不变。尽管，随着用户访问不同网站，缓存表会不时加入新条目，但在很大程度上，数据在整个生命期内将保持不变。为了判断数据是否有效，必须定期查验缓存表；只要细节有所改动，就需要进行更新。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "更新虽然鲜有，但它们还是会发生。另外，如果缓存表被多线程访问，更新过程就需得到妥善保护，以确保各个线程在读取缓存表时，全都见不到失效数据。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "虽然现有的各种并发数据结构经过专门设计，可同时支持并发更新和并发读取（第6 章和第 7 章将给出范例），可是使用它们仍无法完全满足上述的特定需求。\n",
    "\n",
    "我们想要一种数据结构，若线程对其进行更新操作，则并发访问从开始到结束完全排他，及至更新完成，数据结构方可重新被多线程并发访问。所以，若采用 `std::mutex `保护数据结构，则过于严苛，原因是即便没发生改动，它照样会禁止并发访问。我们需在这里采用新类型的互斥。由于新的互斥具有两种不同的使用方式，因此通常被称为读写互斥：允许单独一个“写线程”进行完全排他的访问，也允许多个“读线程”共享数据或并发访问。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "C++17 标准库提供了两种新的互斥：`std::shared_mutex` 和 `std::shared_timed_mutex`。C++14 标准库只有 `std::shared_timed_mutex`，而 C++11 标准库都没有。假如读者的编译器尚未支持 C++14，那么可以考虑使用 Boost 程序库，它也提供了这两个互斥。它们通过提案被纳入 C++标准，提案的原始版本即为 Boost 实现的依据。\n",
    "\n",
    "`std::shared_mutex` 和`std::shared_timed_mutex` 的区别在于，后者支持更多操作（说明见 4.3 节）。所以，若无须进行额外操作，则应选用 `std::shared_mutex`，其在某些平台上可能会带来性能增益。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "第 8 章将清楚地解释这种互斥并非“灵丹妙药”，因为程序性能由下列因素共同决定：处理器的数目，还有读、写线程上的相对工作负荷。多线程令复杂度增加，为了确保性能可以同样随之提升，一个重要的方法是在目标系统上对代码进行性能剖析。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "除了 `std::mutex`，我们也可以利用 `std::shared_mutex` 的实例施加同步操作。更新操作可用 `std::lock_guard<std::shared_mutex>`和 `std::unique_lock<std::shared_mutex>`锁定，代替对应的 `std::mutex` 特化。它们与 `std::mutex` 一样，都保证了访问的排他性质。对于那些无须更新数据结构的线程，可以另行改用共享锁 `std::shared_lock<std::shared_mutex>`实现共享访问。C++14 引入了共享锁的类模板，其工作原理是 RAII 过程，使用方式则与`std::unique_lock` 相同，只不过多个线程能够同时锁住同一个 `std::shared_mutex`。\n",
    "\n",
    "共享锁仅有一个限制，即假设它已被某些线程所持有，若别的线程试图获取排他锁，就会发生阻塞，直到那些线程全都释放该共享锁(1)。反之，如果任一线程持有排他锁，那么其他线程全都无法获取共享锁或排他锁，直到持锁线程将排他锁释放为止。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> (1) 共享锁即读锁，对应 `std::shared_lock<std::shared_mutex>`；排他锁即写锁，对应 `std::lock_guard <std::shared_mutex>`和 `std::unique_lock<std::shared_mutex>`。\n",
    "\n",
    "> AI: \n",
    "> - 共享锁对应读锁，是因为读操作是非破坏性的，可以被多个线程共享；排他锁对应写锁，是因为写操作需要独占资源，防止数据不一致或竞争条件的发生。\n",
    "> - 共享锁和排他锁的互斥规则\n",
    ">   - 如果线程 A 持有共享锁，线程 B 依然可以获取共享锁，但线程 C 无法获取排他锁，必须等到 A 和 B 都释放共享锁。\n",
    ">   - 如果线程 A 持有排他锁，线程 B 和 C 都无法获取共享锁或排他锁，必须等到 A 释放排他锁。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "依照前文描述，代码清单 3.13 是 DNS 缓存表的简略实现，其采用 `std::map` 放置缓存数据，由 `std::shared_mutex` 施加保护。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// 代码清单 3.13 运用 std::shared_mutex 保护数据结构\n",
    "\n",
    "#include <map>\n",
    "#include <mutex>\n",
    "#include <shared_mutex>\n",
    "#include <string>\n",
    "\n",
    "class dns_entry {};\n",
    "\n",
    "class dns_cache {\n",
    "    std::map<std::string, dns_entry> entries;\n",
    "    std::shared_mutex entry_mutex;\n",
    "\n",
    "   public:\n",
    "    dns_entry find_entry(std::string const& domain) {\n",
    "        std::shared_lock<std::shared_mutex> lk(entry_mutex); // 1\n",
    "        std::map<std::string, dns_entry>::const_iterator const it =\n",
    "            entries.find(domain);\n",
    "        return (it == entries.end()) ? dns_entry() : it->second;\n",
    "    }\n",
    "    void update_or_add_entry(std::string const& domain,\n",
    "                             dns_entry const& dns_details) {\n",
    "        std::lock_guard<std::shared_mutex> lk(entry_mutex); // 2\n",
    "        entries[domain] = dns_details;\n",
    "    }\n",
    "};\n",
    "\n",
    "int main() {}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在代码清单 3.13 中，`find_entry()`采用 `std::shared_lock<>`实例保护共享的、只读的访问①，所以多个线程得以同时调用 `find_entry()`。\n",
    "\n",
    "同时，当缓存表需要更新时，`update_or_add_entry()`采用 `std::lock_guard<>`实例进行排他访问②；如果其他线程同时调用`update_or_add_entry()`，那么它们的更新操作将被阻塞，而且调用 `find_entry()`的线程也会被阻塞。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 递归加锁"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "假如线程已经持有某个 `std::mutex` 实例，试图再次对其重新加锁就会出错，将导致未定义行为。但在某些场景中，确有需要让线程在同一互斥上多次重复加锁，而无须解锁。C++标准库为此提供了 `std::recursive_mutex`，其工作方式与 `std::mutex` 相似，不同之处是，其允许同一线程对某互斥的同一实例多次加锁。我们必须先释放全部的锁，才可以让另一个线程锁住该互斥。例如，若我们对它调用了 3 次 `lock()`，就必须调用 3 次`unlock()`。只要正确地使用 `std::lock_guard<std::recursive_mutex>`和 `std::unique_lock<std:: recursive_mutex>`，它们便会处理好递归锁的余下细节。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "假如读者认为需要用到递归锁，然而实际上大多数时候并非如此，那么你的设计很可能需要修改。若要设计一个类以支持多线程并发访问，它就需包含互斥来保护数据成员，递归互斥常常用于这种情形。每个公有函数都需先锁住互斥，然后才进行操作，最后解锁互斥。但有时在某些操作过程中，公有函数需要调用另一公有函数。在这种情况下，后者将同样试图锁住互斥，如果采用 `std::mutex` 便会导致未定义行为。\n",
    "\n",
    "有一种“快刀斩乱麻”的解决方法：用递归互斥代替普通互斥。这容许第二个公有函数成功地对递归互斥加锁，因此函数可以顺利地执行下去。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可是我不推荐上述方法，因为这有可能放纵思维而导致拙劣的设计。具体而言，当以上类型持有锁的时候，其不变量往往会被破坏。也就是说，即便不变量被破坏，只要第二个成员函数被调用，它依然必须工作。我们通常可以采取更好的方法：根据这两个公有函数的共同部分，提取出一个新的私有函数，新函数由这两个公有函数调用，而它假定互斥已经被锁住，遂无须重复加锁1。经过上面的改良设计，读者可以更进一步地仔细推敲，什么情形应当调用新函数，以及数据在该情形中处于什么状态。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3.4 小结"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们在本章中探讨了下列内容：若在线程之间共享数据，条件竞争一旦出现将如何造成灾难；为了防患未然，应该怎样使用互斥 `std::mutex`，以及怎样小心设计接口；我们还分析得知，互斥自身也有问题，会构成死锁，C++标准库为此提供了形式为 `std::lock()`函数的工具，以帮助避免这种情况发生；随后，我们还学习了更深入的防范死锁的方法；接着，我们简要介绍了转移互斥的归属权，还有选择合适的锁粒度的相关议题；最后，我们讲解了另外的数据保护工具，如 `call_once()`和 `std::shared_mutex`，它们适用于特定场景。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可是我还没提及一个议题：等待其他线程的输入。回顾本章的栈容器，虽然它本身是线程安全的，但是，若空栈执行 `pop()`操作就会抛出异常。同样，如果它正处于空栈状态，而某线程等待另一线程传入数值，由于不清楚对方是否已执行 `push()`操作，因此该线程不断试着弹出数值，只要有异常抛出，它就反复尝试（毕竟，我们设计的栈容器具有线程安全的特性，并发读写正是其中一项主要功能，无奈上述线程滥用了这项功能）。检查空栈浪费了原本有用的处理时间，程序却没有进展。事实上，频繁的检查还可能阻滞系统中的其他线程，进而减缓整体运行进度。我们需要某种方法，让目标线程在处理过程中等待另一线程完成任务，却不消耗 CPU 时间。在本章中，我们探讨了保护共享数据的工具，它们构成第 4 章的基础。第 4 章将介绍 C++中几种不同的线程间同步操作；第 6 章会说明如何用这些工具构建更大的、可复用的数据结构。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "name": "C++17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
